package com.jky.stmall.manger;


import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class Tree {
    private static void preOrder1(Node root){
        if(root==null){
            return;
        }
        System.out.print(root.value);
        preOrder1(root.left);
        preOrder1(root.right);
    }
    private static void preOrder2(Node root){
        if (root==null)
            return;
        Stack<Node> stack= new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()){
            Node node=stack.pop();
            System.out.print(node.value);
            if (node.right!=null)
                stack.push(node.right);
            if (node.left!=null)
                stack.push(node.left);
        }
    }
    private static void midOrder1(Node root){
        if (root==null){
            return;
        }
        midOrder1(root.left);
        System.out.print(root.value);
        midOrder1(root.right);

    }
    private static void midOrder2(Node root){
        if (root==null)return;
        Stack<Node> stack= new Stack<>();
        Node cur= root;
        while(!stack.isEmpty()||cur!=null){
            while (cur!=null){
                stack.push(cur);
                cur = cur.left;
            }
            Node node = stack.pop();
            System.out.print(node.value);
            if (node.right!=null) cur=node.right;
        }
    }
    private static void  endOrder1(Node root){
        if (root==null){
            return;
        }
        endOrder1(root.left);
        endOrder1(root.right);
        System.out.print(root.value);
    }
    private static void endOrder2(Node root){
        if (root==null)return;
        Stack<Node> stack2=new Stack<>();
         Stack<Node> stack= new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()){
            Node node= stack.pop();
            stack2.push(node);
            if (node.left!=null){
                stack.push(node.left);
            }
            if (node.right!=null){
                stack.push(node.right);
            }
        }
        while (!stack2.isEmpty()){
            System.out.print(stack2.pop().value);
        }
    }

    //广度优先遍历
    private static void bfs(Node root){
        if (root==null) return;
        Queue<Node> queue=new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()){
            Node node=queue.poll();
            System.out.print(node.value);
            if (node.left!=null){
                queue.add(node.left);
            }
            if (node.right!=null){
                queue.add(node.right);
            }
        }
    }
    public static void main(String[] args) {
        Node nodeA=new Node("A");
        Node nodeB=new Node("B");
        Node nodeC=new Node("C");
        Node nodeD=new Node("D");
        Node nodeE=new Node("E");
        Node nodeF=new Node("F");
        Node nodeG=new Node("G");
        nodeA.left=nodeB;
        nodeA.right=nodeC;
        nodeB.left=nodeD;
        nodeB.right=nodeE;
        nodeC.right=nodeF;
        nodeE.left=nodeG;
        preOrder1(nodeA);
        System                                                                                         .out.println();
        midOrder1(nodeA);
        System.out.println();
        endOrder1(nodeA);

        System.out.println();
        preOrder2(nodeA);
        System.out.println();
        midOrder2(nodeA);
        System.out.println();
        endOrder2(nodeA);

        System.out.println();
        bfs(nodeA);
    }
    public static class Node{
        public String value;
        public Node left;
        public Node right;
        public Node(String value){
            this.value=value;
        }
    }
}
